/*https://leetcode.cn/problems/longest-increasing-subsequence/submissions/563090870/*/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        //dp[i]表示以num[i]为结尾的所有子序列里最长递增子序列的长度
        vector<int> dp(n,0);
        for(int i = 0;i < n;i++){
            //每个元素本身就是一个长度为1的子序列
            dp[i] = 1;
            //以nums[i]为结尾，找到最长的子序列
            for(int j = 0;j < i;j++){
                if(nums[j] < nums[i]){//满足严格递增
                    //由于满足后一位大于前一位,所以最长子序列长度加1
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        int ans = 0;
        for(int i = 0;i < n;i++){
            ans = max(ans,dp[i]);
        }
        return ans;
    }
};